package leetcode.递归回溯BFSDFS;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个没有重复数字的序列，返回其所有可能的全排列。
 * <p>
 * 与 Test40组合总和II【组合总和】类似
 */
public class Test46全排列 {

    public static List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        backtrack(res, new ArrayList<>(), nums, new boolean[nums.length]);
        return res;
    }

    public static void backtrack(List<List<Integer>> res, List<Integer> tempRes,
                                 int[] nums, boolean used[]) {
        if (tempRes.size() == nums.length) {
            //遍历完了.
            res.add(new ArrayList<>(tempRes));
        } else {
            for (int i = 0; i < nums.length; i++) {
                // 设置标志位，检查当前的数组元素是否已经被使用，用来加快判断
                if (!used[i]) {
                    tempRes.add(nums[i]);
                    used[i] = true;
                    backtrack(res, tempRes, nums, used);
                    tempRes.remove(tempRes.size() - 1);
                    // 注意释放
                    used[i] = false;
                }
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {1, 2, 3};
        System.out.println(permute(nums));
    }
}
